#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 500+7;
int g[N][N], dist[N];
bool vis[N];
int main() {
  cin>>n>>m;
  memset(g, 0x3f, sizeof(g));
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  // 以上的初始化你学会了吗？
  while(m--) {
    int x, y, z;
    cin>>x>>y>>z; g[x][y] = min(g[x][y], z);
  }
  // 有重边，取最小的
  for(int i=1; i<=n; ++i) {
    int u = -1;
    for(int j=1; j<=n; ++j) {
      if(!vis[j] && (u==-1 || dist[u]>dist[j])) {
        u = j;
      }
    }
    // 注意if的条件很有讲究
    vis[u] = true;
    for(int j=1; j<=n; ++j) {
      dist[j] = min(dist[j], g[u][j]+dist[u]);
    }
    // 注意更新dist数组的方法
  }
  // 上边这一步最关键了
  // for(int i=1; i<=n; ++i) cout<<dist[i] <<' ';
  cout<<(dist[n]!=0x3f3f3f3f?dist[n]:-1)<<'\n';
  // 最后判定一下是不是真的到了。
}
